package code;

import java.util.ArrayList;
import java.util.List;


public class Triangle {
	
    public int minimumTotal(List<List<Integer>> triangle) {
    	int n=triangle.size();
    	int[][] dp=new int[2][n];
    	if(n==0)	return 0;
    	if(n==1)	return triangle.get(0).get(0);
    	int ans=Integer.MAX_VALUE;
    	dp[0][0]=triangle.get(0).get(0);
    	int index=0;
    	for(int i=1;i<n;i++){
    		for(int j=0;j<=i;j++){
    			if(j==0){
    				dp[(index+1)%2][j]=dp[index%2][j];
    			}
    			else if(j==i){
    				dp[(index+1)%2][j]=dp[index%2][j-1];
    			}
    			else {
    				if(dp[index%2][j]>dp[index%2][j-1])
    					dp[(index+1)%2][j]=dp[index%2][j-1];
    				else dp[(index+1)%2][j]=dp[index%2][j];
    			}
    			dp[(index+1)%2][j]+=triangle.get(i).get(j);
    		}
    		index++;
    		for(int j=0;j<=i;j++)
    			System.out.println(dp[index%2][j]);
    		
    	}
    	for(int i=0;i<n;i++){
    		if(ans>dp[index%2][i])
    			ans=dp[index%2][i];
    	}
        return ans;
    }
	public static void main(String[] args){
		List<List<Integer>> triangle=new ArrayList<List<Integer>>();
		List<Integer> list1=new ArrayList<Integer>();
		list1.add(1);
		List<Integer> list2=new ArrayList<Integer>();
		list2.add(2);
		list2.add(3);
		triangle.add(list1);
		triangle.add(list2);
		Triangle tri=new Triangle();
		System.out.println(tri.minimumTotal(triangle));
	}
}
